﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using Algoritmia.SemiRings;
using Algoritmia.StateSpaces;
using Algoritmia.Schemes.DynamicProgramming;

namespace Algoritmia.Problems.CoinChange
{
    public class KBestCoinChangeProblem : IBackwardsStateSpace<Tuple<int, int>, int>
    {
        private readonly int _Q;
        private readonly Lists.IList<int> _values;
        private readonly int _n;

        public KBestCoinChangeProblem(int Q, Lists.IList<int> values)
        {
            _Q = Q;
            _values = values;
            _n = _values.Count;
        }

        #region Implementation of IBackwardsStateSpace<Tuple<int,int>,int>

        public IEnumerable<Tuple<int, int>> FinalStates
        {
            get { yield return new Tuple<int, int>(_Q, _n); }
        }

        public IEnumerable<int> IncomingDecisions(Tuple<int, int> state)
        {
            int n = state.Item2;
            if (n > 0)
            {
                int q = state.Item1;
                for (int i = 0; _values[n - 1] * i <= q; i++)
                {
                    yield return i;
                }
            }
        }

        public bool IsInitial(Tuple<int, int> state)
        {
            return state.Item1 == 0 && state.Item2 == 0;
        }

        public Tuple<int, int> Undo(Tuple<int, int> state, int decision)
        {
            var q = state.Item1;
            var n = state.Item2;
            return new Tuple<int, int>(q - decision * _values[n - 1], n - 1);
        }

        #endregion
    }

    public class KBestCoinChangeSolver
    {
        private readonly Lists.IList<int> _values;
        private readonly IMap<int, double> _weightsDict;
        private readonly MemoizedDynamicProgrammingSolver<Tuple<int, int>, int, IEnumerable<double>, double> _solver;

        public KBestCoinChangeSolver(Lists.IList<int> values, Lists.IList<double> weights,
            Func<IEnumerable<KeyValuePair<int, double>>, IMap<int, double>> createMap = null)
        {
            _values = values;
            createMap = createMap ?? (it => AlgoritmiaFactory.Maps<int, double>.BuildDefault(it));
            _weightsDict = createMap(_values.Select((e, i) => new KeyValuePair<int, double>(i, weights[i])));
            _solver = new MemoizedDynamicProgrammingSolver<Tuple<int, int>, int, IEnumerable<double>, double>();
        }

        public IEnumerable<double> Solve(int Q, int k)
        {
            var semiRing = new KMinTropicalSemiRing<double>(k);
            return _solver.Solve(new KBestCoinChangeProblem(Q, _values), semiRing, (s, d) => d*_weightsDict[s.Item2]);

        }
    }
}